//================v2要点总结===============
/**
 *  BFS 广度遍历，采用队列的方式
 * 思想： 超级0的思想，由于是从每个0 开始进行搜索的，那么能够被广度遍历到的，距离肯定是最短的
 * https://leetcode-cn.com/problems/01-matrix/solution/01ju-zhen-by-leetcode-solution/
 */


/**
 * @param {number[][]} mat
 * @return {number[][]}
 */
var updateMatrix = function (mat) {

    let r = mat.length
    let c = mat[0].length
    let rsltMat = new Array(r)
    let queue = []

    let dir = [[-1, 0], [0, 1], [1, 0], [0, -1]]

    // 先将所有的0赋值给rsltMat,再将ri,ci加入队列
    for (let ri = 0; ri < r; ri++) {
        rsltMat[ri] = new Array(c).fill(-1)
        for (let ci = 0; ci < c; ci++) {
            if (mat[ri][ci] === 0) {
                rsltMat[ri][ci] = 0
                queue.push([ri, ci])
            }
        }
    }

    while (queue.length) {
        let temp = queue.shift()
        let [ri, ci] = temp
        let tmpVal = rsltMat[ri][ci]
        for (let i = 0; i < dir.length; i++) {
            let tmpR = ri + dir[i][0]
            let tmpC = ci + dir[i][1]
            if (tmpR >= 0 && tmpR < r && tmpC >= 0 && tmpC < c) {
                if (rsltMat[tmpR][tmpC] === -1) {
                    rsltMat[tmpR][tmpC] = tmpVal + 1
                    queue.push([tmpR, tmpC])
                }
            }
        }

    }
    return rsltMat
};

// console.log(updateMatrix([
//     [1, 1, 1],
//     [1, 1, 1],
//     [1, 1, 1],
//     [1, 1, 1],
//     [1, 1, 1],
//     [1, 1, 1],
//     [1, 1, 1],
//     [1, 1, 1],
//     [1, 1, 1],
//     [1, 1, 1],
//     [1, 1, 1],
//     [1, 1, 1],
//     [1, 1, 1],
//     [1, 1, 1],
//     [1, 1, 1],
//     [1, 1, 1],
//     [1, 1, 1],
//     [1, 1, 1],
//     [1, 1, 1],
//     [1, 1, 1],
//     [0, 0, 0]]))

console.log(updateMatrix([
    [1, 1, 1],
    [1, 0, 1],
    [1, 1, 1],
    [1, 1, 1]]))


